This invention relates to an encoder, a decoder, and a method for use in a digital communication system, such as a facsimile transmission system.
In a conventional digital communication system of the type described, a video signal is produced by scanning an item, such as a document, a sheet of drawing, or the like, and converted into a sequence of bits by sampling and analog-to-digital converting the video signal. The bit sequence is, thereafter, encoded into a data-compressed digitized signal consisting of a sequence of binary data so as to be transmitted on a transmission line.
A run-length encoding technique is well known in the art as such as data compression technique. With the run-length encoding technique, the bit sequence is resolved into a plurality of runs, each representative of a continuity of logic "1" levels or logic "0" levels, and is, thereafter, encoded into the digitized signal by measuring each run length.
If long run lengths consecutively appear in the bit sequence, the run-length encoding technique is very effective for the data compression (to be called a compression efficiency) because a total number of runs is remarkably reduced. As to a usual document or drawing, a high compression efficiency is accomplished by the use of the run-length encoding technique. This technique has, therefore, been adopted as an international standard for the facsimile transmission.
In the digital communication system, attempts have been made to transmit and reproduce halftone signals included in the video signal along with signals representative of a black and a white level. It is known in the art that such a halftone can be represented in the video signal by controlling a proportion between the black and the white levels.
A wide variety of dither methods has been proposed to control the proportion between the black and the white levels so as to represent the halftone in the video signal. In each dither method, the video signal has been converted into the bit sequence by the use of one or more dither matrices, each having a plurality of threshold levels which are called dither thresholds and which are intermediate between the black and the white levels of the video signal. The threshold levels are varied periodically in a predetermined order in any one of the dither methods.
As will later be described with reference to a few of several figures of the accompanying drawing, a great deal of runs, each of which has a short run length, inevitably appear in the digitized signal when the dither method is used in combination with the run-length encoding technique. The compression efficiency is, therefore, considerably reduced.
In "Proceeding of the S.I.D." Vol. 17/2 (1976), pp. 92-101, C. N. Judice proposed an ordered dither method wherein the bit sequence derived from the video signal by the use of the dither matrices is rearranged to create long runs of logic "1" levels or logic "0" levels and is, thereafter, encoded into the digitized signal with a data compression technique, such as run-length encoding technique.
With the ordered dither method, a wide memory capacity is indispensable to rearrange the bit sequence into a rearranged bit sequence. In addition, an intricate electronic circuit should be used to implement such an ordered dither method.
Alternatively, a halftone photography method may be used to reproduce the halftone in the facsimile system, instead of the dither methods. However, a lot of short run lengths inevitably take place in the digitized signal when the run-length coding technique is combined with the halftone photography method.